package leetcode.code0955;

import java.util.HashSet;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

// 设计数据的处理流程

//执行用时：2 ms, 在所有 Java 提交中击败了57.86%的用户
//
//内存消耗：41.1 MB, 在所有 Java 提交中击败了47.80%的用户
//
//通过测试用例：147 / 147
public class Solution implements IDebug {

	public int minDeletionSize(String[] strs) {
		Set<Integer> bigs = new HashSet<>();
		bigs.add(0);
		return this.delete(strs, 0, bigs);
	}

	private int delete(String[] strs, int index, Set<Integer> bigs) {
		if (index == strs[0].length()) {
			// 所有index都完成确定顺序
			return 0;
		}
		// 当前index位置的字符严格大于前一个字符串的位置，在index全部比较后，未出现当前index删除的情况下，biger生效，添加到bigs中
		Set<Integer> biger = new HashSet<>();
		int ans = 0;
		for (int i = 1; i < strs.length; i++) {
			char last = strs[i - 1].charAt(index);
			char cur = strs[i].charAt(index);
			// 在之前的index确定当前i位置大于前者字符串，i的后续index都不需要比较同前一个字符的大小。这个是确定大于前一个字符串。
			if (bigs.contains(i)) {
				continue;
			}
			if (cur > last) {
				// 记录严格大于
				biger.add(i);
			}
			if (cur < last) {
				// 逆序了，index列需要删除，biger没有参考价值，不加入bigs
				ans = 1 + this.delete(strs, index + 1, bigs);
				return ans;
			}
		}
		// 如果所有位置都完成严格大于，记录于big中。所有位置都确定顺序
		if (bigs.size() + biger.size() == strs.length) {
			return ans;
		}
		// 当前index生效保留，但是中间存在连续的相等字符，需要后续的确定顺序和删除情况
		bigs.addAll(biger); // 当前bigger是生效的
		ans += this.delete(strs, index + 1, bigs);
		return ans;
	}

	private void minDeletionSize(String[] strs, int L, int R, int index, Set<Integer> deleted) {
		if (L >= R || index == strs.length) {
			return;
		}
		if (deleted.contains(index)) {
			this.minDeletionSize(strs, L, R, index + 1, deleted);
			return;
		}
		boolean equals = false;
		int flag[] = new int[R - L + 1];
		flag[0] = L;
		for (int i = L + 1, p = 1; i <= R; i++, p++) {
			char last = strs[i - 1].charAt(index);
			char cur = strs[i].charAt(index);
			flag[p] = i;
			if (last > cur) {
				deleted.add(index);
				this.minDeletionSize(strs, L, R, index + 1, deleted);
				return;
			} else if (last == cur) {
				equals = true;
				flag[p] = flag[p - 1];
			}
		}
		if (equals) {
			for (int r = 1, l = 0; r < flag.length; r++) {
				if (flag[r] != flag[r - 1]) {
					this.minDeletionSize(strs, l, r - 1, index + 1, deleted);
					l = r;
				}
			}
		}
		return;
	}

	@Override
	public void debug4() {
		H.compare(1, this.minDeletionSize(H.str2array2("[\"xga\",\"xfb\",\"yfa\"]")));
		H.compare(2, this.minDeletionSize(H.str2array2("[\"vdy\",\"vei\",\"zvc\",\"zld\"]")));
		H.compare(1, this.minDeletionSize(H.str2array2("[\"xga\",\"xfb\",\"yfa\"]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		// String str = "abcdefg";
		// System.out.println(str);
		// StringBuffer sb = new StringBuffer(str);
		// System.out.println(sb.reverse().toString());
	}

}
